package com.ly.algorithm.leetcode.binarysearch;

import java.util.Arrays;

/**
 * @Classname Problem34
 * @Description
 *
 * 示例 1：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例 2：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 *
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 *
 * @Date 2020/12/20 19:20
 * @Author 冷心影翼
 */
public class Problem34 {

	public static void main(String[] args) {
		Solution34 solution34 = new Solution34();
		int[] ints = solution34.searchRangeBestWay(new int[]{-1,1,2,2,2,2}, -2);
		System.out.println(Arrays.toString(ints));
	}
}


class Solution34 {
	public int[] searchRange(int[] nums, int target) {
		int l = 0;
		int r = nums.length-1;
		while (l<=r) {
			int mid = l+ (r-l)/2;
			if(nums[mid] == target) {
				int start = mid;
				int end = start+1;
				while (start-1>=0 && nums[start-1] == target) {
					start--;
				}
				while (end<nums.length && nums[end] == target) {
					end++;
				}
				return new int[]{start,--end};
			}else if(nums[mid] < target) {
				l = mid+1;
			}else {
				r = mid-1;
			}
		}
		return new int[]{-1,-1};
	}

	public int[] searchRangeBestWay(int[] nums, int target) {
		int l = 0;
		int r = nums.length-1;
		while (l<=r) {
			int mid = l + (r-l)/2;
			if(nums[mid] == target) {
				r = mid - 1;
			}else if(nums[mid] <target) {
				l = mid + 1;
			}else {
				r = mid - 1;
			}
		}
		int start = l;
		l = 0;
		r = nums.length-1;
		while (l<=r) {
			int mid = l + (r-l)/2;
			if(nums[mid] == target) {
				l = mid+1;
			}else if(nums[mid] <target) {
				l = mid + 1;
			}else {
				r = mid - 1;
			}
		}
		int end = r;
		if(start>= nums.length || nums[start]!=target)
			return new int[]{-1,-1};
		return new int[]{start,end};
	}
}